以下はGemini 3.1 Pro に生成させた解説である。内容のチェックをまだしていない。内容の正しさは無保証。
本稿では、囲碁において特定の石の集合が「無条件生き（相手が連続して何度パスしても絶対に取られない状態）」であることを数学的に定義し、それを計算機的に求めるための基礎理論について解説する。David B. Bensonが1976年に発表した基礎的な定理とアルゴリズムから始め、後にMartin Müllerらが定式化した、領域内に既に存在する相手の死石（無条件死に）を考慮できるように拡張されたアルゴリズムに至るまで、論理的ギャップのない完全な証明を伴って詳述する。
囲碁のルールを数学的に取り扱うために、盤面と石の配置を厳密に定義する。
盤面を有限無向グラフ $G = (V, E)$ とする。ここで $V$ は盤面の交点（格子点）の集合であり、$E$ は隣接する交点を結ぶ線の集合である。点 $u, v \in V$ が隣接していることを $u \sim v$ と表す。
盤面の配置（状態）は、写像 $s: V \to \{\text{Black}, \text{White}, \text{Empty}\}$ によって定まる。本稿では黒石が白石からのいかなる攻撃に対しても取られない状態を評価するため、黒石の集合を $C = s^{-1}(\text{Black})$ とし、黒以外の点（白石および空点）の集合を $U = V \smallsetminus C$ とする。
部分集合 $S \subset V$ について、その近傍 $N(S)$ を以下のように定義する。
$$ N(S) = \{ v \in V \smallsetminus S \mid \text{ある } u \in S \text{ が存在して } u \sim v \} $$これは、集合 $S$ に含まれない点であって、$S$ 内の少なくとも一つの点と直接線で結ばれている点の集合である。
$C$ の極大連結部分集合をブロック（連）と呼び、すべてのブロックからなる族を $\mathcal{B}$ とする。また、$U$ の極大連結部分集合を領域 (region) と呼び、すべての領域からなる族を $\mathcal{R}$ とする。
ブロック $b \in \mathcal{B}$ と領域 $r \in \mathcal{R}$ が隣接するとは、$r \cap N(b) \neq \varnothing$ となることである。
これらの基本概念を用いて、無条件生きを定義するための重要な概念である「不可欠な領域」と「健全な領域」を定義する。
領域 $r \in \mathcal{R}$ がブロック $b \in \mathcal{B}$ にとって不可欠 (vital) であるとは、$r \subset N(b)$ が成り立つことである。
直観的には、これは領域 $r$ を構成するすべての点がブロック $b$ に直接隣接している状態を意味する。すなわち、$r$ は $b$ の石によって完全に囲まれた眼の空間である。
ブロックの族 $X \subset \mathcal{B}$ に対し、領域 $r \in \mathcal{R}$ が $X$ にとって健全 (healthy) であるとは、$r$ に隣接する任意の $b \in X$ について、$r$ が $b$ にとって不可欠 (vital) であることである。
ブロックの族 $X \subset \mathcal{B}$ が無条件生き (unconditionally alive) であるとは、ある領域の族 $Y \subset \mathcal{R}$ が存在して、以下の2つの条件を満たすことである。
与えられた配置における最大の無条件生きブロック集合を求めるためのアルゴリズムは、以下のステップから構成される。
アルゴリズムの正当性を保証する中核となる定理とその完全な証明を以下に示す。
Bensonの無条件生きの条件を満たすブロックの族 $X \subset \mathcal{B}$ と領域の族 $Y \subset \mathcal{R}$ が存在するとき、白がどのように連続して着手しても、$X$ に含まれる任意のブロックは取られることがない。
囲碁における石の捕獲ルールを明確にしておく。ブロック $b \in \mathcal{B}$ が取られるのは、盤面の状態が更新された結果として $N(b) \cap s^{-1}(\text{Empty}) = \varnothing$ となった瞬間である。また、囲碁には自殺手の禁止ルールがあり、打った石を含むブロックのダメ（隣接する空点）が $0$ になる着手は、同時に隣接する相手のブロックのダメを $0$ にして捕獲する場合を除いて禁止されている。（相手の石を取れないにもかかわらず自石を置けるルールを採用した場合でも、直後にその白石は盤面から取り除かれるため、空点を白石で永続的に埋めるという目的は達成できない）。
背理法を用いる。ある状態から黒はすべてパスすると仮定し、白石のみが連続して置かれることで、$X$ に含まれるブロックのうち少なくとも一つが取られると仮定する。そのような白の合法な着手列のうち、最も手数が短いものを考える。
その着手列によって最初に取られる $X$ 内のブロックの一つを $b^*$ とし、$b^*$ が取られる直前の白の着手を $w$ 、その着手が行われる点を $p \in V$ とする。最小手数の仮定より、点 $p$ に白石が置かれる直前の状態において、$X$ に含まれるすべてのブロックは一つも取られずにまだ盤上に存在している。
無条件生きの定義の第2条件より、$b^*$ は $Y$ に含まれる少なくとも2つの異なる領域 $r_1, r_2 \in Y$ に隣接している。さらに第1条件より、$r_1, r_2$ はともに $X$ にとって健全 (healthy) であるため、これらは $b^*$ にとって不可欠 (vital) である。したがって、$r_1 \subset N(b^*)$ および $r_2 \subset N(b^*)$ が成り立つ。
ブロック $b^*$ が取られるためには、その近傍 $N(b^*)$ に含まれるすべての空点に白石が置かれなければならない。$r_1 \subset N(b^*)$ および $r_2 \subset N(b^*)$ であるため、白は $r_1$ と $r_2$ の両方を完全に白石で埋め尽くす必要がある。
白の着手 $w$ によって $b^*$ が取られるということは、点 $p$ は $b^*$ にとっての最後の空点である。白が $r_1$ および $r_2$ を完全に埋め尽くす過程において、それぞれの領域の「最後の1点の空点」を埋める着手が存在しなければならない。一般性を失わず、$r_1$ 内の最後の空点を $q \in r_1$ とし、白が $q$ に着手しようとする局面を考える（もし $p \in r_1$ であれば $p = q$ である）。
点 $q$ に白が着手する直前、$r_1 \smallsetminus \{q\}$ のすべての点はすでに白石で埋まっている。定義より $r_1 \subset U$ は $U$ の極大連結部分集合であるため、$r_1$ の外部と直接繋がる空点は存在しない。したがって、白が $q$ に着手した瞬間、その白石が属するブロックは $r_1$ の内部にも外部にも空点（ダメ）を持たなくなる。
前述の自殺手に関するルールにより、白が $q$ に合法に着手し、かつその石が盤上に残るためには、$q$ に隣接する黒のブロックのいずれかを取らなければならない。$q$ に隣接する黒ブロックを $b'$ とする。
$b'$ は $q \in r_1$ に隣接しているため、$b'$ は領域 $r_1$ に隣接している。仮に $b' \in X$ だとすると、$r_1$ が $X$ にとって健全であるという条件から、$r_1$ は $b'$ にとっても不可欠であり、$r_1 \subset N(b')$ でなければならない。
無条件生きの条件により、$b'$ もまた $Y$ に含まれる少なくとも2つの異なる領域に隣接し、それらは $b'$ にとって不可欠である。そのうちの1つは $r_1$ かもしれないが、少なくとももう1つ、$r_1$ とは異なる領域 $r' \in Y$ が存在する。
最小手数の仮定から、$b'$ を含む $X$ のすべてのブロックはまだ取られておらず、$b'$ のもう一つの不可欠な領域 $r'$ はまだ完全に白石で埋め尽くされていない（なぜなら、$q$ への着手という単一の行動によって、連結成分として互いに独立している $r_1$ と $r'$ の両方の「最後の空点」が同時に埋まることはあり得ないためである）。
ゆえに、$b'$ は $r'$ 内に少なくとも1つの空点（ダメ）を依然として持っており、$q$ に着手しても $b'$ を取ることはできない。
一方で、もし $q$ に隣接する黒ブロックが $X$ に含まれないブロックであった場合、それが取れる可能性はある。しかし、$r_1 \subset N(b^*)$ でありかつ $b^* \in X$ であるため、少なくとも $b^*$ 自身は $q$ と必ず隣接している黒ブロックの一つである。前述の通り、$b^*$ にはもう一つの不可欠な領域 $r_2$ に空点が確実に残っているため、$q$ への着手によって $b^*$ が同時に取られることは決してない。
結果として、$q$ に打たれた白石のダメが $0$ のまま盤上に残ることは不可能であり、$q$ への着手は $b^*$ を取る助けにならない。これにより、白は $r_1$ の最後の1点を埋めることができず、$r_1$ を完全に埋めることができない。同様の論理で、$r_2$ も完全に埋めることはできない。
したがって、白は $b^*$ のすべてのダメを埋めることができず、$b^*$ が取られるという最初の仮定に矛盾する。ゆえに、$X$ に含まれるすべてのブロックは、白がどのように連続して着手しても無条件生きである。 $\blacksquare$
盤面上に一つの黒のブロック $b$ のみが存在し、$b$ の内部に2つの孤立した空点の集合 $r_1, r_2$ （それぞれが完全に独立した1点の空点からなる）が存在する配置を想定する。
このとき、$r_1, r_2$ の周囲の点はすべて $b$ の黒石で囲まれているとする。したがって、$r_1 \subset N(b)$ かつ $r_2 \subset N(b)$ が成り立つ。
ここで、ブロックの族 $X = \{b\}$ 、領域の族 $Y = \{r_1, r_2\}$ と設定する。
以上より、この配置はBensonの無条件生きの2つの条件を完全に満たすため、ブロック $b$ は無条件生きであることが数学的に証明される。これは囲碁における「2眼の石は生き」という経験的な基本法則を、グラフ理論と集合論を用いて厳密に表現したものである。
元のBensonのアルゴリズムでは、黒石で囲まれた領域に空点だけではなく、既に白石が含まれている場合（いわゆる「ナカデ」の途中のような形）を正しく判定できないという問題があった。領域が「空点および白石の繋がり」ではなく、「白石を境界とみなす」ように定義されていたためである。Martin Müllerらはこの問題を解決するため、「無条件死に (unconditionally dead)」の相手の石を内部に含む領域を正しく評価できるようにアルゴリズムを拡張した。
盤面を有限無向グラフ $G = (V, E)$ とする。黒石の極大連結部分集合（ブロック）の族を $\mathcal{B}$ 、白石の極大連結部分集合の族を $\mathcal{W}$ とし、空点の集合を $E_{\text{empty}}$ とする。
黒ブロックの集合 $X \subset \mathcal{B}$ とともに、「すでに死んでいる」とみなす白ブロックの集合 $Z \subset \mathcal{W}$ を同時に考える。集合 $U_{X,Z}$ を以下のように定義する。
$$ U_{X,Z} = E_{\text{empty}} \cup \left( \bigcup_{w \in Z} w \right) $$すなわち、$U_{X,Z}$ はすべての空点と、無条件死にと仮定された白石の和集合である。この $U_{X,Z}$ の極大連結部分集合を「拡張された領域 (extended region)」と呼び、その族を $\mathcal{R}_{X,Z}$ とする。
拡張された領域 $r \in \mathcal{R}_{X,Z}$ が黒ブロック $b \in X$ にとって不可欠 (vital) であるとは、以下の3つの条件をすべて満たすことである。
領域 $r \in \mathcal{R}_{X,Z}$ が $X$ にとって健全 (healthy) であるとは、$r$ に隣接する任意の黒ブロック $b' \in X$ に対して、$r$ が $b'$ にとって不可欠であることである。
組 $(X, Z)$ が以下の条件を満たすとき、$X$ は無条件生きであり、$Z$ は無条件死にである。
上記の条件を満たす組 $(X, Z)$ が存在するとき、黒が連続してパスし、白がどのように連続して着手しても、$X$ に含まれる任意の黒ブロックは取られることがない。
背理法を用いる。白のみが連続して合法手（自殺手でない着手、または相手の石を取る自殺手）を打つことで、$X$ に含まれるブロックのうち少なくとも一つが取られると仮定し、そのような白の着手列の中で最も手数が短いものを考える。最初に取られる $X$ 内のブロックの一つを $b^*$ とし、$b^*$ が取られる直前の白の着手を点 $p \in V$ とする。最小手数の仮定により、点 $p$ に白石が置かれる直前まで、$X$ に含まれるすべてのブロックは一つも取られていない。
条件より、$b^*$ は健全な領域の族 $Y$ に含まれる少なくとも2つの異なる領域 $r_1, r_2$ に隣接しており、これらは $b^*$ にとって不可欠である。不可欠の定義により、$N(r_1) \subset X$ および $N(r_2) \subset X$ が成り立つ。これは、$r_1, r_2$ の外部に直接繋がる空点が存在せず、白が $r_1$ または $r_2$ 内に着手した石は、外部の白石と連結してダメを増やすことができないことを意味する。
ブロック $b^*$ が取られるためには、白は $b^*$ に隣接するすべての空点を白石で埋めなければならない。$r_1$ と $r_2$ はともに少なくとも1つの空点を含み、かつ $b^*$ に隣接しているため、白は $r_1$ および $r_2$ の内部にある空点をすべて白石で埋め尽くす必要がある。
一般性を失わず、領域 $r_1$ において白が最後の1つの空点 $q \in r_1$ に着手しようとする局面を考える。このとき、$r_1 \smallsetminus \{q\}$ に含まれるすべての点はすでに白石で埋まっている（元から $Z$ に属していた白石と、新たに打たれた白石の両方を含む）。$N(r_1) \subset X$ であり、$X$ のブロックはまだ一つも取られていないため、$r_1$ 内の白石の集合は $r_1$ の外部にいかなる空点（ダメ）も持たない。
したがって、白が空点 $q$ に着手した瞬間、$r_1$ 内部の白石全体からなるブロックのダメは $0$ になる。囲碁のルール上、この着手が合法であるためには、$q$ に隣接する黒ブロックのダメを $0$ にして捕獲しなければならない。
$q$ に隣接する黒ブロックを $b'$ とすると、$q \in r_1$ であるため、$b'$ は $r_1$ の境界、すなわち $N(r_1)$ に含まれるか、または $r_1$ 内部に取り残された黒石である。しかし $N(r_1) \subset X$ であり、かつ $r_1$ の内部に黒石は存在しない（$r_1 \subset U_{X,Z}$ の定義より）ため、$b' \in X$ である。
$r_1$ は $X$ にとって健全であるため、$r_1$ は $b'$ にとっても不可欠である。無条件生きの条件より、$b'$ は $r_1$ とは異なるもう一つの不可欠な領域 $r'$ にも隣接している。
最小手数の仮定より、$b'$ のもう一つの領域 $r'$ はまだ完全に白石で埋め尽くされておらず（着手 $q$ によって独立した2つの異なる領域の最後の空点が同時に埋まることはないため）、$b'$ は $r'$ 内に少なくとも1つの空点を持っている。ゆえに、$q$ に着手しても $b'$ のダメは $0$ にならず、$b'$ を取ることはできない。
結果として、白は $q$ に着手すると自身のダメが $0$ になるにもかかわらず黒石を取れないため、この着手は自殺手となりルール上禁止される。これにより、白は $r_1$ の空点を完全に埋め尽くすことができない。同様の論理で $r_2$ も完全に埋めることはできない。
したがって、白は $b^*$ のすべてのダメを埋めることができず、$b^*$ が取られるという仮定に矛盾する。ゆえに、$X$ に含まれるすべてのブロックは無条件生きである。 $\blacksquare$
ある黒のブロック $b$ が大きな陣地を囲っており、その陣地が内部の黒石によって2つの領域 $r_1, r_2$ に分割されているとする。領域 $r_1$ は3目の空点からなり、領域 $r_2$ には既に白石が2つ置かれているが、空点が1つ残っている状態（白石2つ＋空点1つ）を想定する。
元のBensonのアルゴリズムでは、領域は「空点のみの繋がり」として定義されるため、$r_2$ の中に白石が混ざっていると、その白石を境界とする複数の小さな領域に分割されて認識されてしまい、正しく「不可欠な領域」としてカウントできない。
しかし、Müllerによる修正版アルゴリズムでは、死んでいる白石の集合 $Z$ を空点と同等に扱う。そのため、$r_2$ 全体（白石2つと空点1つの和集合）が1つの拡張された領域として認識される。境界 $N(r_2)$ がすべて黒石 $b$ であり、内部に空点が1つ残っているため、この $r_2$ は不可欠な領域の3条件を完全に満たす。結果として、$r_1$ と合わせることで黒ブロック $b$ が無条件生きであることが数学的に正しく証明される。